Some networking equipment has both control and data planes. The control plane constitutes the logical and physical interfaces that do not themselves transport network data but that set up, monitor, and control the activities of silicon that does. In some designs for network processing units (NPUs), an application executes on an operating system such as Linux on the control-plane CPU, governing the operation and performing housekeeping activities on behalf of packet engines, e.g., multi-core processors that receive and forward Internet Protocol packets. The connection between the control-plane CPU and the data/forwarding plane packet engines can be as intimate as a local-bus connection to a coprocessor, as straightforward as standard PCI, or as arm's length as Ethernet or application-specific network fabric.
In the case of a local bus or of PCI, the control processor can treat the forwarding/data plane processors as specialized peripherals that present, superficially, regular memory-mapped interfaces. In the case of a networked connection between the planes, the fabric interface requires a generic driver (for Ethernet, asynchronous transfer mode, etc.), over which specialized command packets are sent to control the packet processor.
Off-the-shelf NPUs strive to integrate high networking functionality closely tied to the control CPU with local connections. Some early designs, however, have suffered from bandwidth limitations at the control point and in the data plane—data packets can face significant bottlenecks in moving both to and from the control plane, as well as among parallel packet engines within the NPU. Moreover, NPUs with powerful and complex packet-engine sets have proven to be difficult to program. See generally, “Linux is on the NPU Control Plane” by Bill Weinberg, EETimes (posted Feb. 5, 2004).
A “partition” is a term used in network traffic shaping. A partition manages bandwidth for a traffic class' aggregate flows, so that all of the flows for the class are controlled together as one. A “flow” is a specific instance of a connection, session, or packet-exchange activity between hosts. And a “traffic class” is a logical grouping of traffic flows that share the same characteristics—a specific application, protocol, address, or set of addresses.
One can use partitions to: (a) protect mission-critical traffic by guaranteeing that a traffic class always gets a defined amount of bandwidth; (b) limit aggressive, non-critical traffic by allowing that traffic class to consume only a defined amount of bandwidth; (c) divide capacity; and (d) assign bandwidth dynamically to users.
All partitions are defined as hierarchical—that is, partitions can contain partitions. This hierarchical approach enables application management for multiple groups, while controlling the group as a whole. For example, an ISP can subdivide a subscriber's partition with child partitions for each of the subscriber's departments. See generally, Packeteer's Packet Guide for PacketWise.
The token bucket algorithm is an algorithm for network traffic shaping or rate limiting. Typically, a token bucket algorithm is used to control the amount of data that is injected into a network, allowing for “bursts” of data to be sent. A related algorithm is the leaky bucket algorithm. The two algorithms differ principally in that the leaky bucket algorithm imposes a hard limit on the data transmission rate, whereas the token bucket algorithm imposes a limit on the average data transmission rate.
Conceptually, the token bucket algorithm employs a token bucket which contains tokens, each of which might represent a unit of bytes. The network administrator specifies for the algorithm how many tokens are needed to transmit how many bytes and a capacity for the token bucket, say b tokens. Then in some embodiments (e.g., those that transmit packets), the algorithm proceeds as follows: (1) a token is added to the bucket every 1/r seconds for some constant rate r; (2) since the bucket can hold at most b tokens, if a token arrives when the bucket is full, the token is discarded; (3) when a packet of n bytes arrives, n tokens are removed from the bucket, and the packet is sent to the network; and (4) if fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.
The algorithm allows bursts of up to b bytes, but over the long run the output of conformant packets is limited to the constant rate, r. A non-conformant packet might be treated in one of the following ways: (a) it might be dropped; (b) it might be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket; or (c) it might be transmitted, but marked as being non-conformant, possibly to be dropped subsequently if the network is overloaded.
Hierarchical token bucket (HTB) is a variation on the token bucket algorithm. HTB was implemented by Martin Devera as part of the Linux kernel; the Linux man page for HTB is tc-htb(8). As its name suggests, HTB involves a number of token buckets arranged in a hierarchy. Devera's implementation apparently builds upon the three-color token bucket algorithm described in RFC 2697, A Single Rate Three Color Marker, (September 1999), published by the Internet Engineering Task Force (IETF).
The traditional approach to multi-threaded and multi-process programming is to use locks to synchronize access to shared resources. Synchronization primitives such as mutexes, semaphores, and critical sections are all mechanisms by which a programmer can ensure that certain sections of code do not execute concurrently if doing so would corrupt shared memory structures. If one thread or process attempts to acquire a lock that is already held by another thread, the thread will block until the lock is free.
In contrast to algorithms that protect access to shared data with locks, lock-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. “Lock-free” refers to the fact that no synchronization primitives such as mutexes or semaphores are involved. Writing a program that uses lock-free data structures is not simply a matter of rewriting the algorithms one would normally protect with a mutex to be lock-free. Because lock-free algorithms are so difficult to write, researchers focus on writing lock-free versions of basic data structures such as stacks, queues, sets, and bash tables. These allow programs to exchange data between threads or processes asynchronously. Typically, lock-free algorithms are written using atomic primitives that the hardware provides. One such primitive is a producer-consumer ring with begin and end pointers, where the producer only updates end pointers after it writes an entry to the ring, and the consumers only update begin pointers after it consumes an entry from the ring. Other hardware-based atomic queuing mechanisms are typically available in multicore processing environments.